#include<vector>
using namespace std;
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int m=coins.size(),n=amount;
        vector<vector<int>>dp(m+1,vector<int>(n+1,0));
        dp[0][0]=1;
        for(int i=1;i<=m;i++){
            for(int j=0;j<=n;j++){
                dp[i][j]=dp[i-1][j];
                if(j-coins[i-1]>=0)
                dp[i][j]+=dp[i][j-coins[i-1]];
            }
        }
        return dp[m][n];
    }
};
//空间优化
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int m=coins.size(),n=amount;
        vector<int>dp(n+1,0);
        dp[0]=1;
        for(int i=1;i<=m;i++)
            for(int j=0;j<=n;j++)
                if(j-coins[i-1]>=0)
                    dp[j]+=dp[j-coins[i-1]];
        return dp[n];
    }
};